package com.wdc.hashtable;

/**
 * 哈希表
 * 1.有限长度，通过拉链 来实现
 * 2. 如果节点的值重复 ，也可以依据存储内容来判断
 */
public class HashTable {
    //节点类
    static class Entry {
        int hash; //哈希码
        Object key; //键

        Object value; // 值
        Entry next;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    Entry[] table = new Entry[16];
    int size = 0;

    /* 求模运算替换为位运算
         - 前提：数组长度是 2 的 n 次方
         - hash % 数组长度 等价于 hash & （数组长度 -1）

     */

    //根据 hash 码获取 value
    Object get(int hash, Object key) {
        //找到hash 码存储的位置
        int idx = hash & (table.length -1);
        if (table[idx] == null){
            return null;
        }
        Entry entry = table[idx];
        while (entry.next != null){
            if (entry.key == key){
                return entry.value;
            }
            entry = entry.next;
        }
        return null;

    }

    //向 hash 表存入新 key value，如果 key  重复 则更新 value
    void put(int hash, Object key, Object value) {
        //确定hash 码对应位置
        int idx = hash & (table.length -1);
        if (table[idx] == null){
            //1. idx 有空位 直接新增
            table[idx] = new Entry(hash, key, value);
        }else {
            // 2. idx 处没有空位，沿链表查找，有重复 key 更新，否则新增
            Entry p = table[idx];
            while (true){
                if (p.key == key){
                    p.value = value;
                    return;
                }
                if (p.next == null){
                    break;
                }
                p = p.next;
            }
            p.next = new Entry(hash, key, value);

        }
        size++;



    }

    // 根据 hash 码删除，返回删除的 value
    Object remove(int hash, Object key) {
        int idx = hash & (table.length -1);
        if (table[idx] == null){
            return null;
        }
        Entry p = table[idx];
        Entry prev = null;
        while (p != null){
            if (p.key == key){
                //找到了 进行删除操作
                if (prev == null){
                    table[idx] = p.next;
                }else {
                    prev.next = p.next;
                }
                size--;
                return p.value;
            }
            prev = p;
            p = p.next;
        }
        return null;
    }

    public static void main(String[] args) {
        System.out.println(9 & 7);
    }

}
